/**
 * 134. 加油站
 * https://leetcode-cn.com/problems/gas-station/
 */
public class Solutions_134 {
    public static void main(String[] args) {
        int[] gas  = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};  // output: 3

//        int[] gas  = {3, 1, 1};
//        int[] cost = {1, 2, 2};  // output: 0

//        int[] gas  = {2, 3, 4};
//        int[] cost = {3, 4, 3};  // output: -1

        int result = canCompleteCircuit(gas, cost);
        System.out.println(result);
    }

    /**
     * // 当前 i 处，获得 gas[i]，但是到达 (i + 1) % len 处，需要花费 cost[i]
     * 3 种情况：
     * 1. gas[i] > cost[i]：可以到达 (i + 1) % len 处，同时油箱中剩余 gas[i] - cost[i]
     * 2. gas[i] == cost[i]：可以到达 (i + 1) % len 处，同时油箱中剩余 0
     * 3. gas[i] < cost[i]：无法到达，只有在 gas[i - 1] + gas[i] >= cost[i - 1] + cost[i] 的情况下，
     *                                  才能从 i 处到达 (i + 1) % len 处，即使用之间剩余的油量
     */
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int cur = 0, rest = 0, res = 0, len = gas.length;
        for (int i = 0; i < len; i++) {
            // i 到 i + 1 后，能够剩余的油量
            cur += gas[i] - cost[i];
            // 一路走来，总共剩余的油量
            rest += gas[i] - cost[i];
            if (cur < 0) {
                // 油量不足，起点尝试设在下一加油站
                res = i + 1;
                cur = 0;
            }
        }
        // 从索引 res 出发，若能够环绕一周，那么最终 rest 最少大于等于 0
        return res < len && rest >= 0 ? res : -1;
    }
}
